package com.wmx.datastructuresandalgorithms.sortalgorithm;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**********************************
 * @author wmx
 * @date 2019/8/30 16:00
 * @description:
 * @version 1.0
 * 快速排序：快速排序就是对冒泡排序的一种改进
 * 通过一趟排序将要排序的数据分成两部分，其中一部分的所有数据都要比较别一部分的所有数据都要小
 * 然后分别将这两两组数据进行快速排序，整个排序过程可以使用到递归，使整个数据变得有序。
 *
 *
 *
 ************************************/
public class QuickSort {
    public static void main(String[] args) {
        int [] arr = {8,3,2,1,7,6,4};
       /* singleFork(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));*/
        /*quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));*/
/*
        int [] arr2 = new int[80000];
        for (int i = 0; i <80000 ; i++) {
            arr2[i] = (int)(Math.random()*800000);
        }
        Date date = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        System.out.println("开始排序的时间："+simpleDateFormat.format(date));
        quickSort(arr2,0,arr2.length-1);
        Date date2 = new Date();
        System.out.println("结束排序的时间："+simpleDateFormat.format(date2));
        System.out.println(Arrays.toString(arr2));*/

        int [] arr3 ={4,1,8,2,7,6,3};
        bothWayFork(arr3,0,arr3.length-1);
        System.out.println(Arrays.toString(arr3));
    }




    public static void quickSort(int[] arr , int let ,int right){
        int center ;
        if(let < right ){
            center = singleFork(arr,let,right);
            quickSort(arr,let,center-1);
            quickSort(arr,center+1,right);
        }
    }


   /** 分割操作
      单向操作   {8,3,2,1,7,6,4} 选准备最后一个数为基准数 ，将i和j都指向let，从左往右j循环 ，j循环范围【let,right】 ,如果遇到一个数小于基准数，
      就将这个数与i下标对应得数据交换，同时i++ ；最后将i下标数跟基准数交换。
      */
    public static int singleFork(int[] arr ,int let ,int right){
        int key ,temp;
        int i ,j ;
        key = arr[right];
        i = let;
        for (j=let;j<=right;j++) {
            if(arr[j]<key){
               temp =arr[i];
               arr[i] =arr[j];
               arr[j] = temp;
               i++;
            }
        }

        arr[right] = arr[i];
        arr[i] = key ;
        return i;
    }






   /**
    * {4,1,8,2,7,6,3};
    * 双向调整 分割数据
    * ①：选择第一个数为基准数，令 i =left+1 ，j = right
    * ②：i 从左往右扫描 ，遇到 大于等于基准数的数停止扫描 i ++，j 从右到左扫描，遇到小于等于基准数的数停止扫描 j++，然后交换两个数位置
    * ③：思考什么时候扫描完呢？当i>=j的时候扫描完成。
    * ④：最后将
    *
   */

    public static int bothWayFork(int [] arr ,int let ,int right) {
        int key, temp;
        int i, j;
        i = let + 1;
        j = right;
        key = arr[0];
        while (true) {
            while ((i <= j) && (arr[i] <= key)) {
                i++;
            }
            while ((i <= j) && (arr[j] >= key)) {
                j--;
            }
            if (i >= j) {
                break;
            }
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;


        }
        arr[let] = arr[j];
        arr[j] = key;
        return j;
    }
}
